package leetcode;

import java.sql.Statement;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class Code128 {
    public static void main(String[] args) {
        System.out.println(new Code128().longestConsecutive(new int[]{
                5, 100, 4, 200, 1, 0, 3, 2
        }));
    }

    /**
     * 优化版
     * @param nums
     * @return
     */
    public static int longestConsecutive2(int[] nums) {
        int res = 0;
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (m.containsKey(num)) continue;
            int left = m.containsKey(num - 1) ? m.get(num - 1) : 0;
            int right = m.containsKey(num + 1) ? m.get(num + 1) : 0;
            int sum = left + right + 1;
            m.put(num, sum);
            res = Math.max(res, sum);
            if (left != 0) {
                m.put(num - left, sum);
            }
            if (right != 0) {
                m.put(num + right, sum);
            }
        }
        return res;
    }

    public int longestConsecutive(int[] nums) {
        HashMap<Integer, Item> map = new HashMap<>();
        int maxLength = 0;
        for (int a = 0; a < nums.length; a++) {
            Item i = map.get(nums[a]);
            if (i == null) {
                i = new Item(-1, 0, 0);
                i.status = -1;
                Item left = map.get(nums[a] - 1);
                Item right = map.get(nums[a] + 1);
                if (left == null) {
                    left = new Item(0, 0, 1);
                } else {
                    left.right = 1;
                }
                if (right == null) {
                    right = new Item(0, 1, 0);
                } else {
                    right.left = 1;
                }
                map.put(nums[a], i);
                map.put(nums[a] - 1, left);
                map.put(nums[a] + 1, right);
                maxLength = getMax(left.right, maxLength, right.left);
            } else if (i.status == -1) {
                continue;
            } else {
                i.status = -1;
                Item left = map.get(nums[a] - i.left - 1);
                if (left == null) {
                    left = new Item(0, 0, i.right + 1);
                    map.put(nums[a] - i.left - 1, left);
                } else {
                    left.right = left.right + i.right + 1;
                }
                Item right = map.get(nums[a] + i.right + 1);
                if (right == null) {
                    right = new Item(0, i.left + 1, 0);
                    map.put(nums[a] + i.right + 1, right);
                } else {
                    right.left = right.left + i.left + 1;
                }
                maxLength = getMax(left.right, maxLength, right.left);
            }
        }
        return maxLength;
    }

    public int getMax(int... item) {
        int max = Integer.MIN_VALUE;
        for (int a : item) {
            if (max < a) {
                max = a;
            }
        }
        return max;
    }

    class Item {
        int status;
        int left;
        int right;

        Item() {
        }

        Item(int status, int left, int right) {
            this.status = status;
            this.left = left;
            this.right = right;
        }
    }
}
